// Created by WXX on 2021/10/28 9:13
#include <iostream>
#include <vector>

using namespace std;

/**
 * 执行用时：376 ms, 在所有 C++ 提交中击败了15.35%的用户
 * 内存消耗：5.9 MB, 在所有 C++ 提交中击败了76.35%的用户
 */
class Solution {
public:

    typedef long long LL;

    vector<int> nums;
    vector<bool> st;

    bool reorderedPowerOf2(int n) {

        while (n) nums.push_back(n % 10), n /= 10;

        st.resize(nums.size(), false);

        return dfs(0, 0);
    }

    bool dfs(int u, LL s) {

        if (u == nums.size()) return check(s);

        for (int i = 0; i < nums.size(); i++)
            if (!st[i]) {
                if (u == 0 && nums[i] == 0) continue;
                st[i] = true;
                s = s * 10 + nums[i];
                if (dfs(u + 1, s)) return true;
                st[i] = false;
                s /= 10;
            }
        return false;
    }

    bool check(LL n) {  // 检查n是否是2的幂次
        return (n & -n) == n;
    }
};

int main() {

    cout << Solution().reorderedPowerOf2(46) << endl;  // true

    return 0;
}
